package com.fanco.learn_datastruct_leetcode.leetcode;

/**
 * 给你一个字符串和一个字符规律p，请你来实现一个支持 '.'和'*'的正则表达式匹配。
 * <p>
 * '.' 匹配任意单个字符
 * '*' 匹配零个或多个前面的那一个元素
 * 所谓匹配，是要涵盖整个字符串s的，而不是部分字符串。
 * <p>
 * 输入：s = "aa" p = "a"
 * 输出：false
 * <p>
 * 输入：s = "aa" p = "a*"
 * 输出：true
 * <p>
 * 输入：s = "ab" p = ".*"
 * 输出：true
 *
 * @author qiaowang 2021/4/23
 */
public class Day07 {
    public static void main(String[] args) {
        Solution solution = new Solution();
        System.out.println(solution.isMatch("ss", "s*"));
    }

    private static class Solution {
        public boolean isMatch(String s, String p) {
            int m = s.length();
            int n = p.length();

            boolean[][] f = new boolean[m + 1][n + 1];
            f[0][0] = true;
            for (int i = 0; i <= m; i++) {
                for (int j = 1; j <= n; j++) {
                    if (p.charAt(j - 1) == '*') {
                        f[i][j] = f[i][j - 2];
                        if (matches(s, p, i, j-1)) {
                            f[i][j] = f[i][j] || f[i-1][j];
                        }
                    } else {
                        if (matches(s, p, i, j)) {
                            f[i][j] = f[i-1][j-1];
                        }
                    }
                }
            }

            return f[m][n];
        }

        public boolean matches(String s, String p, int i, int j) {
            if (i == 0) {
                return false;
            }
            if (p.charAt(j - 1) == '.') {
                return true;
            }
            return s.charAt(i - 1) == p.charAt(j - 1);
        }
    }
}
